package com.sam.sort;

import java.util.Arrays;

/**
 * 排序算法
 * Created by samwang on 2017/11/12.
 */
public class Sort {
    public static void main(String[] args) {
//        int[] testData = {2, 1, 3, 45, 222, 7, 19, 35};
        int[] testData = {2, 1, 3, 4, 6, 7, 5  ,8};
//        bubbleSort(testData);
        radixSort(testData, 1);
//        mergeSort(testData,0,testData.length-1,new int[testData.length]);
        System.out.println("arr = " + Arrays.toString(testData) + "");
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        int temp;
        boolean isChange;//是否发生排序
        for (int i = 0; i < arr.length - 1; i++) {//N-1
            isChange = false;
            for (int j = arr.length - 1; j > i; j--) {//n-i
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    isChange = true;
                }
            }
            if (!isChange) {
                break;
            }
        }
    }

    /**
     * 选择排序
     * @param arr
     */
    public static void selectSort(int[] arr) {
        int minIndex ;
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j=i+1;j<arr.length;j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }


    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {//当前已经有序的数组长度i+1
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }

            }
        }
    }


    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int temp ;
        int incre = arr.length;//每隔多少做一次

        while (true) {
            incre = incre / 2;
            for (int k = 0; k < incre; k++) {

                for (int i = k; i < arr.length; i+=incre) {
                    for (int j = i ; j > k; j-=incre) {
                        if (arr[j] < arr[j-incre]) {
                            temp = arr[j-incre];
                            arr[j-incre] = arr[j];
                            arr[j] = temp;
                        } else {
                            break;
                        }
                    }
                }
            }
            if (incre == 1) {
                break;
            }
        }
    }

    /**
     * 快速的排序
     *
     * @param arr
     * @param l 左起始位置
     * @param r 右起始位置
     */
    public static void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }

        int i = l, j = r;
        int key = arr[l];

        while (i < j) {

            while (i < j && arr[j] >= key) {//从右往左找比key小的
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }

            while (i < j && arr[i] < key) {
                i++;
            }

            if (i < j) {//从左往右找比key大的
                arr[j] = arr[i];
                j--;
            }

        }

        //I == J
        arr[i] = key;
        System.out.println("i = j "+Arrays.toString(arr));
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }

    /**
     *         mergeSort(testData, 0, testData.length-1, new int[testData.length]);
     * @param a
     * @param first
     * @param last
     * @param temp
     */
    public static void mergeSort(int a[],int first,int last,int temp[]){

        if(first < last){
            int middle = (first + last)/2;
            mergeSort(a,first,middle,temp);//左半部分排好序
            mergeSort(a,middle+1,last,temp);//右半部分排好序
            mergeArray(a,first,middle,last,temp); //合并左右部分
        }
    }

    //合并 ：将两个序列a[first-middle],a[middle+1-end]合并
    private static void mergeArray(int a[],int first,int middle,int end,int temp[]){
        int i = first;
        int j = middle+1;
        int k = 0;
        while (i <= middle && j <= end) {
            if (a[i] <= a[j]) {
                temp[k] = a[i];
                k++;
                i++;
            } else {
                temp[k] = a[j];
                k++;
                j++;
            }
        }
        while (i <= middle) {
            temp[k] = a[i];
            k++;
            i++;
        }
        while (j <= end) {
            temp[k] = a[j];
            k++;
            j++;
        }

        for(int ii=0;ii<k;ii++){
            a[first + ii] = temp[ii];
        }
    }



    private static void exchangeElements(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static void heapSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        buildMaxHeap(array);

        for (int i = array.length - 1; i >= 1; i--) {
            exchangeElements(array, 0, i);

            maxHeap(array, i, 0);
        }
    }

    private static void buildMaxHeap(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int half = array.length / 2;
        for (int i = half; i >= 0; i--) {
            maxHeap(array, array.length, i);
        }
    }

    private static void maxHeap(int[] array, int heapSize, int index) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;

        int largest = index;
        if (left < heapSize && array[left] > array[index]) {
            largest = left;
        }

        if (right < heapSize && array[right] > array[largest]) {
            largest = right;
        }

        if (index != largest) {
            exchangeElements(array, index, largest);

            maxHeap(array, heapSize, largest);
        }
    }

    /**
     * 基数排序
     * d表示最大的数有多少位
     *
     * 原理：最后排序最高位的，最大的当然为最大值，最小的为最小值，相等的情况在上一轮的桶排序中已经排好了。
     */
    public static void radixSort(int[] number,int d) {
        int k = 0;//桶排序完后遍历将值赋回数组
        int n = 1;
        int m = 1; //控制键值排序依据在哪一位
        int[][]temp = new int[10][number.length]; //数组的第一维表示可能的余数0-9,即10个桶，第二维存放桶的值
        int[]order = new int[10]; //数组orderp[i]用来表示该位是i的数的个数
        while(m <= d)//从低位到高位做桶排序，一直到第d位
        {
            for(int i = 0; i < number.length; i++){//对某位进行分桶
                int lsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            }

            for (int i = 0; i < 10; i++) {//将桶的值倒装回原数组
                if (order[i] != 0) {//这个桶里有值时
                    for (int j = 0; j < order[i]; k++,j++) {//桶里的值放到数组
                        number[k] = temp[i][j];

                    }
                }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
    }

}
